package com.salim.leetcode.$84;

import java.util.Stack;

public class LargestRectangleInHistogram {
    //解法：https://www.youtube.com/watch?v=RVIh0snn4Qc
    //思路：使用栈 如果下一个柱子高或一样 入栈
    // 如果下一个柱子低 开始计算栈顶柱子的面积 低的柱子以low表示
    //记录当前栈顶为tp
    //面积=（i-1-栈顶）*tp高度 如果栈是空的 长度是i
    //重复以上操作直至栈顶小于等于low
    //入栈low 重复操作
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> indexStack = new Stack<>();
        int i =0;
        int max = 0;
        int height;
        int tp;
        while (i<=heights.length){
            height = (i == heights.length ? 0 : heights[i]);
            if(indexStack.isEmpty()||height>=heights[indexStack.peek()]){
                indexStack.push(i);
                i++;
            }else{
                tp = indexStack.pop();
                max = Math.max((indexStack.isEmpty()?i:(i-1-indexStack.peek()))*heights[tp],max);
            }
        }
        return max;
    }
}
